package problems;

import java.math.BigDecimal;
import java.math.RoundingMode;

import org.junit.Ignore;


/**
 * First try at Euler Project problem 26. Doesn't work. For a working solution, see Euler026.
 * @author laszlo
 *
 */
@Ignore
public class Euler026FirstTry extends AbstractEuler {

	private int SCALE = 10000;
	
	public Number calculate() {
		int maxCycle = 0;
		int maxFor = 2;
		BigDecimal TWO = BigDecimal.ONE.add(BigDecimal.ONE);
		for (BigDecimal d = TWO.setScale(SCALE, RoundingMode.HALF_UP); d.intValue() < 1000; d = d.add(BigDecimal.ONE.setScale(SCALE, RoundingMode.HALF_UP))) {
			BigDecimal fraction = BigDecimal.ONE.setScale(SCALE, RoundingMode.HALF_UP).divide(d, BigDecimal.ROUND_HALF_UP);
			
			StringBuffer decimalPart = new StringBuffer(fraction.stripTrailingZeros().toString().substring(2)); //remove "0."
			while (decimalPart.charAt(0) == '0') {
				decimalPart = decimalPart.deleteCharAt(0);
			}
			
			if (decimalPart.length() < maxCycle) continue;
			if (decimalPart.length() < 9999) continue;
			
			//int thisCycle = 1;

			
			/**			
			int tortoise = 1000, hare = 1001;
			
			while (decimalPart.charAt(tortoise) != decimalPart.charAt(hare)) {
				tortoise++;
				hare+=2;
			}
			
			for (hare = tortoise, tortoise = 1000; decimalPart.charAt(tortoise) != decimalPart.charAt(hare); tortoise++, hare++, thisCycle++ ) {
				System.out.println("tortoise at " + tortoise + ", hare at " + hare + ", ");
			}
			
			**/
			
			int thisCycle = getCycleLength(1, decimalPart);

			
			if (thisCycle > maxCycle) {
				maxCycle = thisCycle;
				maxFor = d.intValue();
				System.out.println("new max cycle length " + maxCycle + " for 1/" + d.stripTrailingZeros());
			}
			
			System.out.println(d.setScale(0) + ", cycle " + thisCycle + ": " + fraction.stripTrailingZeros());
		}      
		
		return maxFor;
	}
	
	private int getCycleLength(int startLength, StringBuffer decimalPart) {
		/*
	    # The main phase of the algorithm, finding a repetition x_mu = x_2mu
	    # The hare moves twice as quickly as the tortoise
	    tortoise, hare = f(x0), f(f(x0)) # f(x0) is the element/node next to x0.
	    while tortoise != hare:
	        tortoise = f(tortoise)
	        hare = f(f(hare))

		 */
		
		int tortoise = 1001;
		int hare = tortoise + startLength;
		while (decimalPart.charAt(tortoise) != decimalPart.charAt(hare)) {
			tortoise++;
			hare += 2;
		}
		
		/*
		# at this point the start of the loop is equvi-distant from current tortoise
		# position and x0, so hare (set to tortoise-current position) moving in
		# circle and tortoise (set to x0 ) moving towards circle, will intersect at
		# the beginning of the circle.
		 
		# Find the position of the first repetition of length mu
		# The hare and tortoise move at the same speeds
		mu = 0
		tortoise, hare = x0, tortoise
		while tortoise != hare:
		    tortoise = f(tortoise)
		    hare = f(hare)
		    mu += 1
		*/
		
		int mu = 0;
		tortoise = 1000;
		hare = tortoise;
		while (decimalPart.charAt(tortoise) != decimalPart.charAt(hare)) {
			tortoise++;
			hare++;
			mu++;
		}
		
		/*
	    # Find the length of the shortest cycle starting from x_mu
	    # The hare moves while the tortoise stays still
	    lam = 1
	    hare = f(tortoise)
	    while tortoise != hare:
	        hare = f(hare)
	        lam += 1
	 
	    return lam, mu
		*/
		
		int thisCycle = startLength;
		hare = tortoise + 1;
		while (decimalPart.charAt(tortoise) != decimalPart.charAt(hare)) {
			hare++;
			thisCycle++;
		}
		
		//check if every number of the cycle corresponds to (its position+thisCycle)
		for (int i = 1; i <= thisCycle; i++) {
			if (decimalPart.charAt(tortoise + i) != decimalPart.charAt(tortoise + thisCycle + i)) {
				System.out.println("in " + decimalPart.toString().substring(1000, 2000) + ", cycle was detected as " + thisCycle + ", but char at " + (tortoise+i) + " is not equal to " + (tortoise + thisCycle + i));
				System.out.println("cycle length is not " + thisCycle + ", retrying");
				return getCycleLength(thisCycle + 1, decimalPart);
			}
		}
		
		return thisCycle;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 983;
	}
	
}
